package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-10-21 17:26
 **/
public class LeetCode459 {

    public boolean repeatedSubstringPattern2(String s) {
        String str = s + s;
        return str.substring(1, str.length() - 1).contains(s);
    }

    public boolean repeatedSubstringPattern(String s) {
        int len = s.length();
        int[] next = getNext(s);
        return next[len - 1] != 0 && len % (len - next[len - 1]) == 0;
    }

    public int[] getNext(String str) {
        int len = str.length();
        int[] next = new int[len];
        int i = 0;
        int j = 1;
        for (; j < len; j++) {
            while (i > 0 && str.charAt(i) != str.charAt(j)) {
                i = next[i - 1];
            }
            if (str.charAt(i) == str.charAt(j)) {
                i++;
            }
            next[j] = i;
        }
        return next;
    }

    public static void main(String[] args) {
        LeetCode459 code = new LeetCode459();
        boolean b = code.repeatedSubstringPattern("abab");
        System.out.println("b = " + b);

    }

}
